package leetcode;
import java.util.*;
//复习册

public class Num_0 {

    public static void main(String[] args) {
        int[] arr = {3,5,1,2,1,6,10,4,9,4,7,8};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //插入排序法
    public static void insertSort(int[] arr) {
        //待排序区间
        for(int i = 1; i < arr.length; i++){
            //已排序区间
            for(int j = i; j > 0 && arr[j] < arr[j-1]; j--){
                swap(arr, j, j - 1);
            }
        }
    }

    //二分插入排序
    public static void insertSortBS(int[] arr) {
        //待排序区间
        for(int i = 1; i < arr.length; i++){
            //二分查找以排序区间[0, i-1]
            //还需要确保排序的稳定性
            int left = 0;
            int right = i - 1;
            int mid = right / 2;
            //找到那个刚好比arr[i]大的那个元素的位置
            // 3 3 4 6 7 7 ---2 插到mid-1 = right
            //3 插到
            while(left < right){
                mid = left + (right - left) / 2;
                if(arr[i] < arr[mid]){
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }
        }
    }

    public static void main1(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        while(!queue.isEmpty()){
            int count = queue.size();//当前一行的所有可能性
            while(count-- != 0){
                //看里面每一个可能所导致的结果，然后如果满足就入队
                int x = queue.poll();//把这次的可能导出来，看这个能造成神魔样的结果

                //如果满足某种条件
                queue.offer(5);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}